package simple;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个字符串s和t，判断它们是否是同构的。
 *
 * 如果s中的字符可以按某种映射关系替换得到t，那么这两个字符串是同构的。
 *
 * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
 *
 * 链接：https://leetcode.cn/problems/isomorphic-strings
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class IsomorphicStrings {
    /**
     * 时间复杂度O(n)
     * 这道题很显然就是需要保存两者之间的印射关系，自然联想到了Map
     * 使用map来保存两个字符串的每个字符的映射关系，然后当出现映射关系不一致时，说明不为同构字符串
     * */
    class Solution {
        public boolean isIsomorphic(String s, String t) {
            Map<Character, Character> map = new HashMap<>(s.length());
            Map<Character, Character> map1 = new HashMap<>(s.length());
            for (int i = 0; i < s.length(); i++) {
                char currentChar = s.charAt(i);
                char currentChar1 = t.charAt(i);
                if(map.containsKey(currentChar) && map.get(currentChar) != currentChar1){
                    return false;
                }
                if(map1.containsKey(currentChar1) && map1.get(currentChar1) != currentChar){
                    return false;
                }
                map.put(currentChar, currentChar1);
                map1.put(currentChar1, currentChar);
            }
            return true;
        }
    }

    /**
     * 时间复杂度O(n) 但是比上一个方法要快不少，因为是数组存放，直接寻址，比hash寻址快
     * 异口同声法（自命名）
     * 异口：指的s和t分别是不同的语言
     * 同声：将s和t翻译成一样的语言，如果值一样，说明s和t是同构字符串
     * 举个例子，s是法语、t是中文，那么将这两句话翻译为英语，如果为同构，那么英语的意思是一样的，否则就不是同构。
     *
     * 所以很多字符串比较的题目 都可以使用128大小的数组解决
     * */
    class Solution1 {
        public boolean isIsomorphic(String s, String t) {
            // 题目规定字符串中的字符都为ASCII码,所以初始化大小为128，默认值全部为0
            // 可以理解为，mapS存放的是s翻译成的英语，mapT是t翻译成的英语
            int[] mapS = new int[128];
            int[] mapT = new int[128];

            for(int i = 0; i < s.length(); i++){
                char c1 = s.charAt(i);
                char c2 = t.charAt(i);
                // 比较翻译后的内容是否一致，如果不一致就返回false
                if(mapS[c1] != mapT[c2]){
                    return false;
                }else if(mapS[c1] == 0){
                    // 如果为0说明还是未经翻译的
                    mapS[c1] = i + 1;
                    mapT[c2] = i + 1;
                }
            }
            return true;
        }
    }
}
